const int N = 2e7 + 5;
char s[N], t[N];
int d[N], ans;
void manacher() {
	ans = 0;
	int len = 0;
	t[len] = '$'; t[++len] = '#';
	for (int i = 0, p = strlen(s); i < p; i++) {
		t[++len] = s[i];
		t[++len] = '#';
	}
	for (int i = 1; i <= len; i++) {
		d[i] = 0;
	}
	t[++len] = '@';
	d[1] = 1;
	for (int i = 1, l = 1, r = 1; i <= len; i++) {
		if (i <= r) {
			d[i] = min(r - i + 1, d[r - i + l]);
		}
		while (t[i - d[i]] == t[i + d[i]]) {
			d[i]++;
		}
		if (i + d[i] - 1 > r) {
			l = i - d[i] + 1;
			r = i + d[i] - 1;
		}
		ans = max(ans, d[i] - 1);
	}
}